<html>
<head>
<link rel="shortcut icon" href="./favicon.ico">
<link rel="stylesheet" type="text/css" href="./style.css">
<link rel="canonical" href="./Remainder_Integer_Signed.html">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="Computes the signed remainder of the signed dividend and divisor, and uses the status of each iterated subtraction to control the [Quotient](./Quotient_Integer_Signed.html) module. Part of the [Signed Integer Divider](./Divider_Integer_Signed.html) module.  **Not really usable by itself.** But if you want to do so, be sure to short-circuit the control handshake interface.">
<title>Remainder Integer Signed</title>
</head>
<body>

<p class="inline bordered"><b><a href="./Remainder_Integer_Signed.v">Source</a></b></p>
<p class="inline bordered"><b><a href="./legal.html">License</a></b></p>
<p class="inline bordered"><b><a href="./index.html">Index</a></b></p>

<h1>Signed Integer Remainder</h1>
<p>Computes the signed remainder of the signed dividend and divisor, and uses
 the status of each iterated subtraction to control the
 <a href="./Quotient_Integer_Signed.html">Quotient</a> module. Part of the <a href="./Divider_Integer_Signed.html">Signed
 Integer Divider</a> module.  <strong>Not really
 usable by itself.</strong> But if you want to do so, be sure to short-circuit the
 control handshake interface.</p>
<h2>Interface</h2>
<p>The calculation starts after any pending results have been read out by the
 output ready/valid handshake, and an input ready/valid handshake provides
 a new dividend and divisor. Each calculation step is synchronized with the
 Quotient module through a control handshake.</p>
<h2>Theory of Operation</h2>
<p>Think of the <code>dividend</code> and <code>divisor</code> as points along a number line.
 Depending on their initial signs, we will iteratively add or subtract the
 largest possible multiple of <code>divisor</code> to/from the <code>dividend</code> as necessary
 <em>to bring the <code>dividend</code> towards zero without passing zero</em>. No initial
 calculations of absolute values or final sign corrections are necessary,
 which saves a lot of hardware and cycles.</p>
<h2>Ports and Constants</h2>

<pre>
`default_nettype none

module <a href="./Remainder_Integer_Signed.html">Remainder_Integer_Signed</a>
#(
    parameter WORD_WIDTH        = 0,
    parameter STEP_WORD_WIDTH   = 0
)
(
    input  wire                     clock,
    input  wire                     clear,

    input  wire                     input_valid,
    output reg                      input_ready,
    input  wire [WORD_WIDTH-1:0]    dividend,
    input  wire [WORD_WIDTH-1:0]    divisor,

    output reg                      output_valid,
    input  wire                     output_ready,
    output wire [WORD_WIDTH-1:0]    remainder,
    output wire                     divide_by_zero,
    
    output reg                      control_valid,
    input  wire                     control_ready,
    output reg                      step_ok
);

    `include "<a href="./clog2_function.html">clog2_function</a>.vh"

    localparam WORD_ZERO = {WORD_WIDTH{1'b0}};

    initial begin
        input_ready      = 1'b0;
        output_valid     = 1'b0;
        control_valid    = 1'b0;
        step_ok          = 1'b0;
    end
</pre>

<p>Some basic definitions to establish our two's-complement signed
 representation.</p>

<pre>
    localparam ADD              = 1'b0;
    localparam SUB              = 1'b1;
    localparam POSITIVE         = 1'b0;
    localparam NEGATIVE         = 1'b1;
</pre>

<p>We have to internally compute with one extra bit of range to allow the
 minimum signed number to be expressible as an unsigned number. Else, we
 cannot subtract any multiple of itself from this minimum signed number.
 For example, <code>-8 / 1</code> needs to add <code>+8</code> to the remainder to reach
 a remainder of <code>0</code>, and with the minimum number of bits (4) to represent
 <code>-8</code>, we can only represent up to <code>+7</code>.</p>

<pre>
    localparam WORD_WIDTH_LONG  = WORD_WIDTH + 1;
    localparam WORD_ZERO_LONG   = {WORD_WIDTH_LONG{1'b0}};
    localparam WORD_ONE_LONG    = {{WORD_WIDTH_LONG-1{1'b0}},1'b1};
    localparam WORD_ONES_LONG   = {WORD_WIDTH_LONG{1'b1}};
</pre>

<p>We must then also increase the step word width by one to avoid an
 unnecessary extra calculation step. See the <a href="./Adder_Subtractor_Binary_Multiprecision.html">Multiprecision
 Adder/Subtractor</a> module for
 details.</p>

<pre>
    localparam STEP_WORD_WIDTH_LONG = STEP_WORD_WIDTH + 1;
</pre>

<h2>Data Path</h2>
<h3>Divisor Storage and Shifting</h3>

<pre>
    wire [WORD_WIDTH_LONG-1:0] divisor_long;

    <a href="./Width_Adjuster.html">Width_Adjuster</a>
    #(
        .WORD_WIDTH_IN  (WORD_WIDTH),
        .SIGNED         (1),
        .WORD_WIDTH_OUT (WORD_WIDTH_LONG)
    )
    divisor_extend
    (
        .original_input     (divisor),
        .adjusted_output    (divisor_long)
    );
</pre>

<p>Extract and store the initial sign of the divisor.</p>

<pre>
    reg  divisor_sign_initial_load = 1'b0;
    wire divisor_sign_initial;

    <a href="./Register.html">Register</a>
    #(
        .WORD_WIDTH     (1),
        .RESET_VALUE    (1'b0)
    )
    divisor_sign_initial_storage
    (
        .clock          (clock),
        .clock_enable   (divisor_sign_initial_load),
        .clear          (1'b0),
        .data_in        (divisor_long [WORD_WIDTH_LONG-1]),
        .data_out       (divisor_sign_initial)
    );
</pre>

<p>Store the divisor aside and shift its LSB into the MSB of the
 remainder_increment at each division step, while sign-extending the
 divisor. The initial load does the first shift implicitly.</p>
<p><strong>NOTE:</strong> We do the signed shift right manually rather than use the Verilog
 operator "&gt;&gt;&gt;" since that would need us to declare <code>divisor_long</code>, and only
 it, as signed, which is asking for unexpected bugs.</p>

<pre>
    reg                         divisor_enable  = 1'b0;
    reg                         divisor_load    = 1'b0;
    wire [WORD_WIDTH_LONG-1:0]  divisor_loaded;
    reg  [WORD_WIDTH_LONG-1:0]  divisor_initial = WORD_ZERO_LONG;
    reg  [WORD_WIDTH_LONG-1:0]  divisor_next    = WORD_ZERO_LONG;

    always @(*) begin
        divisor_initial = {divisor_long [WORD_WIDTH_LONG-1], divisor_long [WORD_WIDTH_LONG-1:1]};
    end

    <a href="./Register_Pipeline.html">Register_Pipeline</a>
    #(
        .WORD_WIDTH     (WORD_WIDTH_LONG),
        .PIPE_DEPTH     (1),
        .RESET_VALUES   (WORD_ZERO_LONG)
    )
    divisor_storage
    (
        .clock          (clock),
        .clock_enable   (divisor_enable),
        .clear          (1'b0),
        .parallel_load  (divisor_load),
        .parallel_in    (divisor_initial),
        // verilator lint_off PINCONNECTEMPTY
        .parallel_out   (),
        // verilator lint_on  PINCONNECTEMPTY
        .pipe_in        (divisor_next),
        .pipe_out       (divisor_loaded)
    );
</pre>

<h3>Remainder Increment Storage and Shifting</h3>
<p>The initial shift into the MSB is done at load.</p>

<pre>
    reg                         remainder_increment_enable  = 1'b0;
    reg                         remainder_increment_load    = 1'b0;
    wire [WORD_WIDTH_LONG-1:0]  remainder_increment_loaded;
    reg  [WORD_WIDTH_LONG-1:0]  remainder_increment_initial = WORD_ZERO_LONG;
    reg  [WORD_WIDTH_LONG-1:0]  remainder_increment_next    = WORD_ZERO_LONG;

    always @(*) begin
        remainder_increment_initial = {divisor_long [0], WORD_ZERO};
    end

    <a href="./Register_Pipeline.html">Register_Pipeline</a>
    #(
        .WORD_WIDTH     (WORD_WIDTH_LONG),
        .PIPE_DEPTH     (1),
        .RESET_VALUES   (WORD_ZERO_LONG)
    )
    remainder_increment_storage
    (
        .clock          (clock),
        .clock_enable   (remainder_increment_enable),
        .clear          (1'b0),
        .parallel_load  (remainder_increment_load),
        .parallel_in    (remainder_increment_initial),
        // verilator lint_off PINCONNECTEMPTY
        .parallel_out   (),
        // verilator lint_on  PINCONNECTEMPTY
        .pipe_in        (remainder_increment_next),
        .pipe_out       (remainder_increment_loaded)
    );
</pre>

<h3>Dividend Sign Storage</h3>

<pre>
    wire [WORD_WIDTH_LONG-1:0] dividend_long;

    <a href="./Width_Adjuster.html">Width_Adjuster</a>
    #(
        .WORD_WIDTH_IN  (WORD_WIDTH),
        .SIGNED         (1),
        .WORD_WIDTH_OUT (WORD_WIDTH_LONG)
    )
    dividend_extend
    (
        // It's possible some input bits are truncated away
        // verilator lint_off UNUSED
        .original_input     (dividend),
        // verilator lint_on  UNUSED
        .adjusted_output    (dividend_long)
    );
</pre>

<p>Extract the initial sign of the dividend.</p>

<pre>
    reg  dividend_sign_initial_load = 1'b0;
    wire dividend_sign_initial;

    <a href="./Register.html">Register</a>
    #(
        .WORD_WIDTH     (1),
        .RESET_VALUE    (1'b0)
    )
    dividend_sign_initial_storage
    (
        .clock          (clock),
        .clock_enable   (dividend_sign_initial_load),
        .clear          (clear),
        .data_in        (dividend_long [WORD_WIDTH_LONG-1]),
        .data_out       (dividend_sign_initial)
    );
</pre>

<h3>Remainder Storage and Shifting</h3>
<p>The <code>dividend</code> (numerator of a fraction) is stored as the <code>remainder</code> of
 the division. We repeatedly add/subtract the <code>remainder_increment</code> unless
 the <code>remainder</code> would become too small and flip its sign.</p>

<pre>
    reg                         remainder_enable = 1'b0;
    reg                         remainder_load   = 1'b0;
    wire [WORD_WIDTH_LONG-1:0]  remainder_loaded;
    wire [WORD_WIDTH_LONG-1:0]  remainder_next;

    <a href="./Register_Pipeline.html">Register_Pipeline</a>
    #(
        .WORD_WIDTH     (WORD_WIDTH_LONG),
        .PIPE_DEPTH     (1),
        .RESET_VALUES   (WORD_ZERO_LONG)
    )
    remainder_storage
    (
        .clock          (clock),
        .clock_enable   (remainder_enable),
        .clear          (1'b0),
        .parallel_load  (remainder_load),
        .parallel_in    (dividend_long),
        // verilator lint_off PINCONNECTEMPTY
        .parallel_out   (),
        // verilator lint_on  PINCONNECTEMPTY
        .pipe_in        (remainder_next),
        .pipe_out       (remainder_loaded)
    );

    <a href="./Width_Adjuster.html">Width_Adjuster</a>
    #(
        .WORD_WIDTH_IN  (WORD_WIDTH_LONG),
        .SIGNED         (1),
        .WORD_WIDTH_OUT (WORD_WIDTH)
    )
    remainder_shorten
    (
        .original_input     (remainder_loaded),
        .adjusted_output    (remainder)
    );
</pre>

<h3>Remainder Calculations</h3>
<p>Shift the LSB of the divisor into the MSB of the remainder_increment.
 Shifts are signed, and done manually to avoid Verilog pitfalls.</p>

<pre>
    always @(*) begin
        divisor_next             = {divisor_loaded [WORD_WIDTH_LONG-1], divisor_loaded [WORD_WIDTH_LONG-1:1]};
        remainder_increment_next = {divisor_loaded [0], remainder_increment_loaded [WORD_WIDTH_LONG-1:1]};
    end
</pre>

<p>Now, depending on the divisor sign, check the contents of divisor to see if
 there are still non-sign bits in it, which means the remainder_increment is
 invalid, and check if the sign of the remainder_increment does not match
 the sign of the divisor, which means we also haven't yet shifted enough
 bits into the remainder_increment to make it a valid number.</p>
<p><strong>NOTE:</strong> The bit reduction when testing if the divisor only contains sign
 bits may end up being a critical path (but a high-speed one). It's not
 currently pipelinable without major control changes.</p>

<pre>
    reg remainder_increment_sign  = 1'b0;
    reg divisor_all_sign_bits     = 1'b0;
    reg remainder_increment_valid = 1'b0;

    always @(*) begin
        remainder_increment_sign  = remainder_increment_loaded [WORD_WIDTH_LONG-1];
        divisor_all_sign_bits     = (divisor_sign_initial == POSITIVE) ? (divisor_loaded == WORD_ZERO_LONG) : (divisor_loaded == WORD_ONES_LONG);
        remainder_increment_valid = (remainder_increment_sign == divisor_sign_initial) && (divisor_all_sign_bits == 1'b1);
    end
</pre>

<p>Then apply the remainder_increment to the remainder</p>

<pre>
    reg remainder_add_sub = 1'b0;

    always @(*) begin
        remainder_add_sub = (divisor_sign_initial == dividend_sign_initial) ? SUB : ADD;
    end

    reg  remainder_input_valid = 1'b0;
    // wire remainder_input_ready;
    wire remainder_output_valid;
    reg  remainder_output_ready = 1'b0;

    wire remainder_next_overflow;

    <a href="./Adder_Subtractor_Binary_Multiprecision.html">Adder_Subtractor_Binary_Multiprecision</a>
    #(
        .WORD_WIDTH         (WORD_WIDTH_LONG),
        .STEP_WORD_WIDTH    (STEP_WORD_WIDTH_LONG)
    )
    remainder_calc
    (
        .clock              (clock),
        .clock_enable       (1'b1),
        .clear              (clear),

        .input_valid        (remainder_input_valid),
        //verilator lint_off PINCONNECTEMPTY
        .input_ready        (),
        //verilator lint_on  PINCONNECTEMPTY

        .add_sub            (remainder_add_sub), // 0/1 -> A+B/A-B
        .A                  (remainder_loaded),
        .B                  (remainder_increment_loaded),

        .output_valid       (remainder_output_valid),
        .output_ready       (remainder_output_ready),

        .sum                (remainder_next),
        // verilator lint_off PINCONNECTEMPTY
        .carry_out  (),
        .carries    (),
        // verilator lint_on  PINCONNECTEMPTY
        .overflow   (remainder_next_overflow)
    );
</pre>

<p>If the next division step would overshoot past zero and change the sign of
 the remainder, meaning too much was added/subtracted, then this division
 step does nothing.</p>
<p><strong>NOTE:</strong> The bit reduction when testing if the remainder has reached zero
 exactly may end up being a critical path (but a high-speed one). It's not
 currently pipelinable without major control changes.</p>

<pre>
    reg remainder_next_valid = 1'b0;

    always @(*) begin
        remainder_next_valid = ((remainder_next [WORD_WIDTH_LONG-1] == dividend_sign_initial) && (remainder_next_overflow == 1'b0)) || (remainder_next == WORD_ZERO_LONG);
    end
</pre>

<p>And report if we tried to divide by zero. We do this after the pipeline
 since it's a reduction operation. We can load this at the end of the first
 calculation step.</p>
<p>We have to reconstruct the initially loaded divisor by undoing the first
 shift into the remainder increment at load time.</p>

<pre>
    reg divisor_is_zero     = 1'b0;
    reg divide_by_zero_load = 1'b0;

    always @(*) begin
        divisor_is_zero = ({divisor_loaded [0 +: WORD_WIDTH], remainder_increment_loaded [WORD_WIDTH_LONG-1]} == WORD_ZERO_LONG);
    end

    <a href="./Register.html">Register</a>
    #(
        .WORD_WIDTH     (1),
        .RESET_VALUE    (1'b0)
    )
    divide_by_zero_storage
    (
        .clock          (clock),
        .clock_enable   (divide_by_zero_load),
        .clear          (clear),
        .data_in        (divisor_is_zero),
        .data_out       (divide_by_zero)
    );
</pre>

<h2>Control Path</h2>
<h3>States and Storage</h3>
<p>We denote state as two bits, with the following transitions:
 LOAD -&gt; CALC -&gt; DONE -&gt; LOAD -&gt; ... 
 We don't handle the fourth, impossible case.
 The state encoding is arbitrary.</p>

<pre>
    localparam                      STATE_WIDTH     = 2;
    localparam [STATE_WIDTH-1:0]    STATE_LOAD      = 2'b00;
    localparam [STATE_WIDTH-1:0]    STATE_CALC      = 2'b10;
    localparam [STATE_WIDTH-1:0]    STATE_DONE      = 2'b11;
    localparam [STATE_WIDTH-1:0]    STATE_ERROR     = 2'b01; // Never reached
</pre>

<p>The state bits, from which we derive the control outputs and the internal
 control signals.</p>

<pre>
    reg  [STATE_WIDTH-1:0]  state_next = STATE_LOAD;
    wire [STATE_WIDTH-1:0]  state;

    <a href="./Register.html">Register</a>
    #(
        .WORD_WIDTH     (STATE_WIDTH),
        .RESET_VALUE    (STATE_LOAD)
    )
    state_storage
    (
        .clock          (clock),
        .clock_enable   (1'b1),
        .clear          (clear),
        .data_in        (state_next),
        .data_out       (state)
    );
</pre>

<h3>Calculation Steps</h3>
<p>Each division takes <code>WORD_WIDTH_LONG</code> steps, from <code>WORD_WIDTH_LONG-1</code> to <code>0</code>, plus
 one step to initially load the dividend and divisor. Thus, we need
 a counter of the correct width.</p>

<pre>
    localparam STEPS_WIDTH      = clog2(WORD_WIDTH_LONG);
    localparam STEPS_INITIAL    = WORD_WIDTH_LONG - 1;
    localparam STEPS_ZERO       = {STEPS_WIDTH{1'b0}};
    localparam STEPS_ONE        = {{STEPS_WIDTH-1{1'b0}},1'b1};
</pre>

<p>Count down WORD_WIDTH-1 calculation steps. Stops at zero, and reloads when
 leaving STATE_LOAD.</p>

<pre>
    reg                     calculation_step_clear  = 1'b0;
    reg                     calculation_step_do     = 1'b0;
    wire [STEPS_WIDTH-1:0]  calculation_step;

    <a href="./Counter_Binary.html">Counter_Binary</a>
    #(
        .WORD_WIDTH     (STEPS_WIDTH),
        .INCREMENT      (STEPS_ONE),
        .INITIAL_COUNT  (STEPS_INITIAL [STEPS_WIDTH-1:0])
    )
    calculation_steps
    (
        .clock          (clock),
        .clear          (calculation_step_clear),

        .up_down        (1'b1),         // 0/1 -> up/down
        .run            (calculation_step_do),

        .load           (1'b0),
        .load_count     (STEPS_ZERO),

        .carry_in       (1'b0),
        // verilator lint_off PINCONNECTEMPTY
        .carry_out      (),
        .carries        (),
        .overflow       (),
        // verilator lint_on  PINCONNECTEMPTY
        .count          (calculation_step)
    );
</pre>

<h3>Input/Output/Control Handshakes</h3>
<p>Accept inputs when empty (after results are read out) or frehsly
 reset/cleared). Declare outputs valid when calculation is done.  Perform
 a control handshake each time the addition/subtraction is complete.</p>

<pre>
    always @(*) begin
        output_valid   = (state == STATE_DONE);
        input_ready    = (state == STATE_LOAD);
        control_valid  = (state == STATE_CALC) && (remainder_output_valid == 1'b1);
    end
</pre>

<h3>Control Events</h3>

<pre>
    reg load_inputs       = 1'b0; // When we load the dividend and divisor.
    reg read_outputs      = 1'b0; // When we read out the remainder.
    reg read_control      = 1'b0; // When other computations acknowledge the calculation step.
    reg calculating       = 1'b0; // High while performing the division steps.
    reg step_done         = 1'b0; // High when a calculation exits the adder/subtractor.
    reg first_calculation = 1'b0; // High during the first calculation step.
    reg last_calculation  = 1'b0; // High during the last calculation step.

    always @(*) begin
        load_inputs       = (input_ready   == 1'b1) && (input_valid   == 1'b1);
        read_outputs      = (output_valid  == 1'b1) && (output_ready  == 1'b1);
        read_control      = (control_valid == 1'b1) && (control_ready == 1'b1);
        calculating       = (state == STATE_CALC);
        step_done         = (read_control == 1'b1);
        first_calculation = (read_control == 1'b1) && (calculation_step == STEPS_INITIAL [STEPS_WIDTH-1:0]);
        last_calculation  = (read_control == 1'b1) && (calculation_step == STEPS_ZERO);
    end
</pre>

<p>Past this point, we should not refer directly to the FSM states,
 but to these events which are combinations of states and signals.</p>
<h3>State Transitions</h3>
<p>There is no handling of erroneous states.</p>

<pre>
    always @(*) begin
        state_next = (load_inputs       == 1'b1) ? STATE_CALC : state;
        state_next = (last_calculation  == 1'b1) ? STATE_DONE : state_next;
        state_next = (read_outputs      == 1'b1) ? STATE_LOAD : state_next;
    end
</pre>

<h3>Calculation Step Status</h3>
<p>Signal to the Quotient module if this calculation step was valid. </p>

<pre>
    always @(*) begin
        step_ok = (remainder_next_valid == 1'b1) && (remainder_increment_valid == 1'b1) && (calculating == 1'b1) && (step_done == 1'b1);
    end
</pre>

<h3>Calculation Step Control</h3>

<pre>
    always @(*) begin
        calculation_step_clear = (load_inputs == 1'b1) || (clear == 1'b1);
        calculation_step_do    = (step_done   == 1'b1);
    end
</pre>

<p>Adder/Subtractor Control</p>

<pre>
    always @(*) begin
        remainder_input_valid  = (calculating   == 1'b1);
        remainder_output_ready = (control_ready == 1'b1);
    end
</pre>

<p>Divisor and Remainder Increment Control</p>

<pre>
    always @(*) begin
        divide_by_zero_load         = (first_calculation == 1'b1);
        divisor_load                = (load_inputs    == 1'b1);
        divisor_enable              = (load_inputs    == 1'b1) || ((calculating == 1'b1) && (step_done == 1'b1));
        divisor_sign_initial_load   = (load_inputs    == 1'b1);
        remainder_increment_load    = (divisor_load   == 1'b1);
        remainder_increment_enable  = (divisor_enable == 1'b1);
    end
</pre>

<p>Dividend and the Remainder Control</p>

<pre>
    always @(*) begin
        dividend_sign_initial_load  = (load_inputs == 1'b1);
        remainder_load              = (load_inputs == 1'b1);
        remainder_enable            = (load_inputs == 1'b1) || ((step_ok == 1'b1) && (step_done == 1'b1));
    end

endmodule 
</pre>

<hr>
<p><a href="./index.html">Back to FPGA Design Elements</a>
<center><a href="https://fpgacpu.ca/">fpgacpu.ca</a></center>
</body>
</html>

